# 前缀和——矩阵区域的和
class Solution1:
    def matrixBlockSum(self, mat: List[List[int]], k: int) -> List[List[int]]:
        m,n = len(mat),len(mat[0])
        answer = [[0]*n for _ in range(m)]

        # 预处理二维前缀和数组
        dp = [[0]*(n+1)for _ in range(m+1)]
        for i in range(1,m+1):
            for j in range(1,n+1):
                dp[i][j] = dp[i][j-1] + dp[i-1][j]+mat[i-1][j-1]-dp[i-1][j-1]

        # 使用前缀和数组
        for i in range(0,m):
            for j in range(0,n):
                x1,y1 = max(0,i-k) + 1,max(0,j-k) + 1
                x2,y2 = min(m-1,i+k) + 1,min(n-1,j+k) + 1
                answer[i][j] = dp[x2][y2] - dp[x2][y1-1] - dp[x1-1][y2] + dp[x1-1][y1-1]
        return answer

# 位运算——位1的个数
class Solution2:
    def hammingWeight(self, n: int) -> int:
        ret = 0
        while n:
            n &= (n-1)
            ret += 1
        return ret

# 比特位计数
class Solution3:
    def countBits(self, n: int) -> List[int]:
        ret = []
        for i in range(0,n+1):
            tmp,count = i,0
            while tmp:
                tmp &=(tmp-1)
                count+=1
            ret.append(count)
        return ret

# 汉明距离
class Solution4:
    def hammingDistance(self, x: int, y: int) -> int:
        # 异或之后，相同为0，不同为1，只需要遍历s的比特位，看看有多少个1
        s, ret = x^y, 0
        while s:
            s &=(s-1)
            ret+=1
        return ret

# 只出现一次的数
class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        ret = 0
        for i in nums:
            ret ^= i
        return ret

# 只出现一次的数2
class Solution:
    def singleNumber(self, nums: List[int]) -> List[int]:
        tmp = 0
        for i in nums:
            tmp ^= i
        tmp &= (-tmp)
        x1,x2 = 0,0
        for i in nums:
            if i & tmp:
                x1 ^= i
            else:
                x2 ^= i
        return [x1,x2]<Paste>

# 判定字符是否唯一
class Solution:
    def isUnique(self, astr: str) -> bool:
        if len(astr) > 26 :
            return False
        mark = 0
        for e in astr:
            index = ord(e) - ord('a')
            if ((mark >> index) & 1) == 1 :
                return False;
            else:
                mark |= (1<<index)
        return True

# 丢失的数字
class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        mark = 0
        for i in nums:
            mark ^= i
        for i in range(0,len(nums)+1):
            mark ^= i
        return mark
